home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / formats / gif / floyd.txt < prev    next >
Encoding:
Internet Message Format  |  1988-03-21  |  4.3 KB
  1. From: awpaeth@watcgl.waterloo.edu (Alan W. Paeth)
  2. Subject: Floyd-Steinberg Notes
  3. Date: 11 Jan 88 22:52:04 GMT
  4. In article <2709@aramis.rutgers.edu> (Lou Steinberg) writes:
  5. >
  6. >I should point out that the actual fractions we used were, assuming
  7. >you are at X, moving left to right:
  8. >
  9. >                 X    7/16
  10. >         3/16   5/16  1/16    
  11. >
  12. >Note that the error goes to four neighbors, not three.  I think this
  13. >will probably do better (at least for black and white)...
  14.  
  15. It does noticeably better. I implemented both on the Alto (606x808 one-bit
  16. monochromatic display, think Macintosh) for a Smalltalk page layout system at
  17. Xerox in the late 70's. The *true* 4-way algorithm gave "crisper" images with
  18. a better contrast range and edge definition, and easily justifies the error
  19. pass to the fourth neighbor.
  20.  
  21. The additional computing can be minimized by keeping the errors to be written
  22. to the next scan line in three registers, and then using some clever loop
  23. unrolling is used so that only one read/write access to the error array need
  24. occur (this array maintains the error for the next consecutive scanline).
  25. The remaining code is the inter-register shuffling of the error fractions.
  26.  
  27. As someone else pointed out, bit shifting can be used to generate the error
  28. values, but it is *VERY* important that the distributed fractions sum to one
  29. exactly. As a non-intuitive example: (x/2)+(x/2) is not equal to x, for x odd,
  30. using integer math (whether you shift or divide, round or chop). A proper
  31. implementation would form the values as "x/2" and "x-(x/2)". Failing this,
  32. there is a potential error in the LSB. This is worse than just some imprecision
  33. in any single pixel. As this error continues to accumulate, it can eventually
  34. bias a pixel to become "whiter than white", so that even a fully-white pixel
  35. fails to remove this bogus white error. A typical symptom is diagonal streaking
  36. away from fully white objects. A less-severe problem is that shifting of
  37. negative values is not the same as division by powers of two, leading to some
  38. asymmetries in imaging largely black vs white scenes, but if proper accounting
  39. of the error is done, this does not give rise to spatial errors.
  40.  
  41. When table lookup is not expensive, four error tables can be precomputed, and
  42. properly computed values placed in each table. A fully table driven system
  43. require no multiplies or divides, and can additionally perform the algorithm
  44. as described in my last posting, can use Heckbert's method, perform tone
  45. reproduction curve correction, etc., all in one imaging pass.
  46.  
  47. >...I've not tried it with color.
  48.  
  49. It works beautifully. As with b/w, there must be output pixels as bright and
  50. dark as the max and minimum values in the scene, or the "spill-overflow"
  51. described above occurs. These bounds must occur independently for each color
  52. component, to allow the error to be reduced simultaneously for each primary.
  53. This implies that at least eight output pixels (the corners of the color cube
  54. -- the bounding rectangle for all candidate input pixels) must be available on
  55. output to avoid any spatial spill-over.
  56.  
  57. Our lab has used such a Floyd-Steinbert IMaging tool to map 24bit RGB into 3 
  58. bits, which were then packed both spatially and by planes into a 2048x2048x32
  59. Adage framebuffer, which allowed us about 20 seconds (at 15Hz) zoom-pan-scroll
  60. animation to preview scenes from a ray-tracing feature film, prior to an
  61. expensive production run.
  62.  
  63. I mention all this because one noticible visual artifact in "screening" the
  64. movie was the scintillation of the "noise" bits during previewing, when
  65. moving temporally through frames. I tried a few cuts at an extended 3D
  66. Floyd-Steinber error diffusion algorithm which would additionally pass errors
  67. onto the same (x,y) pixel one frame forward in *time*, in an effort to reduce
  68. this blinking effect. I am quite interested to hear if anyone else has explored
  69. such an extension to the dimensionality of error diffusion.
  70.  
  71. I'm convinced that there is a lot of good milage left in the Floyd-Steinberg
  72. approach (I consider it a larger topic than merely any one algorithm), and
  73. am interested in receiving further comments.
  74.  
  75.     /Alan Paeth
  76.     Computer Graphics Laboratory
  77.     University of Waterloo
  78.  
  79.